package algorithmExample.BinarySearch;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/11 10:43
 */
public class FindMinRotatedSortedArray {
    public int findMin(int[] nums) {
        int right = 0, left = nums.length - 1;
        while (right <= left) {
            int medium = (right + left) / 2;
            if (medium == nums.length - 1) {
                break;
            }
            if (nums[medium] > nums[medium + 1]) {
                return nums[medium + 1];
            }
            if (nums[left] < nums[medium]) {
                right = medium;
            } else if (nums[left] > nums[medium]) {
                left = medium;
            } else {
                //等于的情况下
                left = left - 1;
            }

        }
        return nums[0];
    }


    public static void main(String[] args) {
//        int[] input = new int[]{10,1,10,10,10};
//        int[] input = new int[]{2,3,4,5,0,1};
//        int[] input = new int[]{1,2,3,4,5};
        int[] input = new int[]{10, 10, 1, 10, 10};
        int result = new FindMinRotatedSortedArray().findMin(input);
        System.out.println("the min of input is " + result);
    }
}
